package 纯数组;

public class JZ53零到N中缺失的数字II {

    /**
     * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，
     * 并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
     *
     * 示例 1:
     * 输入: [0,1,3]
     * 输出: 2
     * 示例 2:
     * 输入: [0,1,2,3,4,5,6,7,9]
     * 输出: 8
     *
     * 限制：
     * 1 <= 数组长度 <= 10000
     */

    public int missingNumber(int[] nums) {

        int left=0;
        int right=nums.length-1;
        int mid;

        while (left<=right){
            mid=(right-left)/2+left;
            int num=nums[mid];

            if(num==mid){
                left=mid+1;
            }else if(num>mid){
                //左边
                right=mid-1;
            }else{
                //右边
                left=mid+1;
            }
        }

        return left;
    }

    public static void main(String[] args) {
        JZ53零到N中缺失的数字II jz=new JZ53零到N中缺失的数字II();
        int[] arr={1};
        int result = jz.missingNumber(arr);
        System.out.println(result);
    }

}
